package com.lwg.datastructure.dynamicPrograming;

import java.util.Arrays;

/**
 * FileNmae: PackageProblenms1.java
 *
 * @Description: All rights Reserved, Designed By Sunyard
 * Copyright: Copyright(C) 2020-2022
 * Company  : Sunyard.hangzhou
 * @author: 李炜光
 * @slogan:
 * @Date: 2021/10/22 0022
 */
public class PackageProblenms1 {

    public static void main(String[] args) {
        System.out.println("最终结果是：" + packageProblem1());
        System.out.println("最终结果2是：" + packageProblem2());
    }

    public static int packageProblem1() {
        int packageContainWeight = 4;//包最大可装重量
        int[] weight = {1, 4, 3};//3个物品的重量
        int[] value = {150, 300, 200};//3个物品的价值

        //数组的长度加一是为了保证数组的长度为4 比如说int[4] 包含的有4个数 0,1,2.3,4，但是0的数组置为0
        int[][] dp = new int[weight.length + 1][packageContainWeight + 1];
        //System.out.println(dp[0][0]);
        dp[0][0] = 0;
        for (int i = 1; i <= value.length; i++) {
            for (int j = 1; j <= packageContainWeight; j++) {
                //数组下标从0开始，故第i个物品的重量为weight[i-1]  在数组weight中的i-1就相当于 dp[]的第i个
                if (j < weight[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
                }
            }
        }
        return dp[weight.length][packageContainWeight];
    }

    public static int packageProblem2() {
        int packageContainWeight = 4;//包最大可装重量
        int[] weight = {1, 4, 3};//3个物品的重量
        int[] value = {150, 300, 200};//3个物品的价值

        //数组的长度加一是为了保证数组的长度为4 比如说int[4] 包含的有4个数 0,1,2.3,4，但是0的数组置为0
        int[] dp = new int[packageContainWeight + 1];
        //System.out.println(dp[0][0]);
        dp[0] = 0;
        for (int i = 0; i < value.length; i++) {
        //for (int i = 1; i <= value.length; i++) {
            for (int j = packageContainWeight; j >=1; j--) {
                if (j>=weight[i]){
                    //数组下标从0开始，故第i个物品的重量为weight[i-1]  在数组weight中的i-1就相当于 dp[]的第i个
                    //dp[j] = Math.max(dp[j], dp[j - weight[i-1]] + value[i-1]);
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                    System.out.println(Arrays.toString(dp)+j);
                }
            }
            //System.out.println(Arrays.toString(dp));
        }
        return dp[packageContainWeight];
    }
}
